Concepto de Árboles (página 2)

Partes: 1, 2

Árboles Binarios

Un árbol binario
T se define como un conjunto finito de elementos, llamados
nodos, de forma que:

T es vacío ( en cuyo caso se llama
árbol nulo o árbol vació) o
T contiene un nodo distinguido R, llamado
raíz de T, y los restantes nodos de T forman un par
ordenado de árboles binarios disjuntos T1 y
T2.

Si T contiene una raíz R, los dos
árboles T1 y T2 se llaman, respectivamente,
subárboles izquierdo y derecho de la raíz R. Si
T1 no es vació , entonces su raíz se llama
sucesor izquierdo de R; y análogamente, si T2 no es
vació, su raíz se llama sucesor derecho de
R.

Observe que :

B es un sucesor izquierdo y C un sucesor derecho del
nodo A.
El subárbol izquierdo de la raíz A
consiste en los nodos B, D, E y F, y el subárbol derecho
de A consiste en los nodos C , G, H, J, K y L.

Figura (1)

Cualquier nodo N de un árbol binario T tiene 0, 1
ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores,
los nodos R y J sólo tienen un sucesor , y los nodos D,F,
G,L y K no tienen sucesores. Los nodos sin sucesores se llaman
nodos terminales.

La definición anterior del árbol binario T
es recursiva, ya que T se define en términos de los
subárboles binarios T1 y T2. Esto significa, en
particular, que cada nodo N de T contiene un subárbol
izquierdo y uno derecho. Más aun, si N es un nodo
terminal, ambos árboles están
vacíos.

Dos árboles binarios T y T’ se dicen que
son similares si tienen la misma estructura o,
en otras palabras, si tienen la misma forma. Los árboles
se dice que son copias si son similares y tienen los mismos
contenidos en sus correspondientes nodos.

Terminología

Frecuentemente se usa una
terminología de relaciones familiares para describir las
relaciones entre los nodos de un árbol T. En particular,
suponga que N es un nodo de T con un sucesor izquierdo S1 y un
sucesor derecho S2. Entonces N se llama padre de S1 y S2.
Análogamente, S1 se llama el hijo izquierdo de N y S2 el
hijo derecho de N. Es mas, S1 y S2 se dice que son hermanos. Cada
nodo N de un árbol binario T, excepto la raíz,
tiene un único padre, llamado predecesor de N.

Los términos descendientes y antecesor tienen su
significado usual. Así, un nodo L se dice descendiente de
un nodo N ( y N se dice antecesor de L) si existe una
sucesión de hijos desde N hasta L. En particular, L se
dice descendiente izquierdo o derecho de N dependiendo de si
pertenece al subárbol izquierdo o al derecho de
N.

También se usa esa terminología de
teoría
de grafos y de
horticultura para un árbol binario T.
específicamente, la línea dibujada entre un nodo N
de T y un sucesor suyo se llama ariste, y una secuencia de
aristas consecutivas se denomina camino. Un nodo terminal se
llama hoja y un camino que termina en una hoja se llama
rama.

Cada nodo de un árbol binario T tiene asignado un
número de nivel, de la forma que sigue. A la raíz R
del árbol T se le asigna el numero de nivel 0, y al resto
de los nodos se le asigna un numero de nivel que es mayor en 1
que el numero de nivel de su padre. Más aun, aquellos
nodos con el mismo número de nivel se dice que pertenecen
a la misma generación.

La profundidad o altura (o altura) de un árbol T
es el número máximo de nodos de una rama de T.
Equivale a 1 más que el mayor numero de nivel de
T.

Dos árboles binarios T y T’ se dice que son
similares si tienen la misma estructura o , en otras palabras, si
tienen la misma forma. Los árboles se dice que son copias
si son similares y tienen los mismos contenidos en sus
correspondientes nodos.

La terminología de relaciones familiares, de
teoría de grafos y horticultura se usa para los
árboles generales de la misma forma que para los
árboles binarios. En particular, si N es un nodo con
sucesores S 1, S 2,…, S m, se dice que N es el padre de
los S i , los S i son hijos de N y los S i son hermanos unos de
otros.

El termino "árbol" aparece, con significados
ligeramente diferentes, en muchas áreas diferentes de las
matemáticas y de la informática. Aquí asumimos que
nuestro árbol general T esta enraizado, es decir, que T
tiene un nodo distinguido R llamado raíz de T; y que T
esta ordenado, ósea, que los hijos de cada nodo N de T
tienen un orden especifico. Estas dos propiedades no se requieren
siempre para definir un árbol.

Ejemplo:

La figura muestra un
árbol general T con 13 nodos,

A,B,C,D,E,F,G,H,J,K,L,M,N

A menos de que se indique lo contrario, la
raíz de un árbol T es el nodo en lo alto del
diagrama, y
los hijos de un nodo están ordenados de izquierda a
derecha. Así, A es la raíz de T y A tiene tres
hijos; el primer hijo B, el segundo C y el tercero D. se observa
que:

El nodo C tiene tres hijos.
Cada uno de los nodos B y K tienen dos
hijos.
Cada uno de los nodos D y H tiene un
hijo.
Los nodos E,F,G,L,J,M y N no tienen
hijos.

El último grupo de
nodos, los que no tienen hijos, se llaman nodos
terminales.

Un árbol binario T’ no es un
caso especial de un árbol general T: los árboles
binarios y los árboles generales son dos cosas distintas.
Las dos diferencias básicas son:

un árbol binario T’ puede estar
vació, pero un árbol general T no es
vació.
Suponga que un nodo N tiene un solo hijo. Entonces el
hijo se distingue por ser el izquierdo o el derecho en un
árbol binario T’, mientras que no existe esa
distinción en un árbol general T.

Figura (2)

Árboles binarios
Completos.

Considere un árbol binario T. El
árbol binario T se dice que es completo si todos sus
niveles, excepto posiblemente el ultimo, tienen el máximo
numero de nodos posibles y si todos lo9s nodos del ultimo nivel
están situados. Lo más posible a la izquierda.
Así, solo existe un único árbol completo Tn
con exactamente n nodos.

Representación de los árboles
generales en la
computadora.

Suponga que T es un árbol general. A
menos que se diga lo contrario, T se mantendrá en memoria en
términos de una representación enlazada que usa
tres arrays paralelos, INFO, HIJO, (o ABAJO) Y HERM (u HORIZ), y
una variable puntero RAIZ, tal como sigue. En primer lugar, cada
nodo N de T corresponderá a una posición K tal
que:

INFO [ K ] contiene los datos del nodo
N.
HIJO [ K ] contiene la posición del primer
hijo de N. La condición HIJO [ K ]= NULO indica que N no
tiene hijos.
HERM [ K ] contiene la posición del siguiente
hermano de N. La condición HERM [ K ] = NULO indica que
N es el ultimo hijo de su padre.

Ejemplo:

Considere el árbol general T de la figura (2) ,
suponga que los datos de los nodos de T se guardan en un Array
INFO como en la figura (3) las relaciones estructurales de T se
obtienen asignando valores al
puntero RAIZ y a los Arrays HIJO y HERM tal y como
sigue:

como la raíz A de T se guarda en INFO [ 2 ],
se y hace RAIZ:= 2.
Como el primer hijo de A es el nodo B, guardado en
INFO [3 ], se hace HIJO [ 2 ]:= 3. como A no tiene hermanos, se
hace HERM [ 2 ]= NULO.
Como el primer hijo de B es el nodo E, guardado en
INFO [ 15 ], se hace HIJO [3]:= 15. como el nodo C es el
siguiente hermano de B y C se guarda en INFO [ 4 ], se hace
HERM [3]:=4.

Y así sucesivamente. La figura (3) da los valores
finales de HIJO y HERM. Observe que la lista DISP de nodos vacos
se mantiene en el primer array, hijo, donde DISP = 1.

Figura (3)

Árboles
Generales.

Un árbol general ( a veces es
llamado árbol ) se define como un conjunto, finito no
vació T de elementos, llamados nodos, tales
que:

T contiene un elemento distinguido R, llamado
raíz de T.
Los restantes elementos de T forman una
colección ordenada de cero o mas árboles
disjuntos T1, T2,.., Tm..

Figura (4)

Árboles Binarios de
búsqueda.

Esta sección discute una de las
estructuras de
datos más importantes de la informática, el
árbol binario de búsqueda. Esta estructura permite
buscar y encontrar un elemento con una media de tiempo de
ejecución f (n) = 0 ( log2 n), también permite
insertar y borrar elementos fácilmente. Esta estructura
contrasta con las siguientes estructuras:

Array lineal ordenado. Aquí se puede buscar y
encontrar un elemento con un tiempo de ejecución f(n) =
(log2n), pero es costoso el insertar y borrar
elementos.
Lista enlazada. Aquí se puede insertar y
borrar elementos fácilmente, pero es costoso el buscar y
encontrar un elemento, ya que se debe usar una búsqueda
secuencial.

Aunque cada nodo de un árbol binario de
búsqueda puede contener un registro entero
de datos, la definición del árbol binario depende
de un campo dado cuyos valores son distintos y deben estar
ordenados.

Supongamos que T es un árbol binario. Entonces T
se dice que es un árbol binario de búsqueda ( o
árbol binario ordenado) si cada nodo N de T tiene la
siguiente propiedad: el
valor de N es
mayor que cualquier valor del subárbol izquierdo de N y es
menor que cualquier valor del subárbol derecho de N. ( no
es difícil ver que esta propiedad garantiza el recorrido
inorden de T dará una lista ordenada de los elementos de
T) .

Conclusión.

De este trabajo se
podría decir que un árbol binario se define como un
conjunto finito de elementos llamados nodos. En estos casos se
puede usar terminología de relaciones familiares para
descubrir las relaciones entre los nodos de un árbol; y
que un árbol puede ser implementado fácilmente en
una computadora.

Es bueno hacer énfasis en esto ya que se puede
saber mucho sobre lo que tiene que ver con los árboles;
entre las cosas que podemos mencionar se encuentra la
raíz, los nodos de un árbol y la diferencia entre
nodos sucesores y nodos terminales, como se muestran en el
contenido del trabajo.

Bibliografía